﻿#define DDCL_CORE

#include "ddclmap.h"
#include "ddclmalloc.h"

#include <stdlib.h>
#include <string.h>
#include <memory.h>


static dduint32
_hashfunc_AP(const char * dat, size_t size){
     dduint32 hash = 0xAAAAAAAA;
    for(size_t i = 0; i < size; i++){
        if ((i & 1) == 0)
            hash ^= ((hash << 7) ^ dat[i] * (hash >> 3));
        else
            hash ^= (~((hash << 11) + dat[i] ^ (hash >> 5)));
    }
    return hash;
}

static dduint32
_hashfunc_RS(const char * dat, size_t size){
    int b = 378551; int a = 63689;
    dduint32 hash = 0;
    for(size_t i = 0; i < size; i++){
        hash = hash * a + dat[i];
        a = a * b;
    }
    return hash;
}

static dduint32
_hashfunc_JS(const char * dat, size_t size){
     dduint32 hash = 1315423911;
    for(size_t i = 0; i < size; i++)
        hash ^= ((hash << 5) + dat[i] + (hash >> 2));
    return hash;
}

static dduint32
_hashfunc_PJW(const char * dat, size_t size){
    dduint32 BitsInUnsignedInt = (dduint32)(4 * 8);
    dduint32 ThreeQuarters     = (dduint32)((BitsInUnsignedInt  * 3) / 4);
    dduint32 OneEighth         = (dduint32)(BitsInUnsignedInt / 8);
    dduint32 HighBits          = (dduint32)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
    dduint32 hash = 0;  dduint32 test = 0;
    for(size_t i = 0; i < size; i++){
        hash = (hash << OneEighth) + dat[i];
        if((test = hash & HighBits)  != 0){
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
    return hash;
}

static dduint32
_hashfunc_ELF(const char * dat, size_t size){
     dduint32 hash = 0;  dduint32 x = 0;
    for(size_t i = 0; i < size; i++){
        hash = (hash << 4) + dat[i];
        if((x = hash & 0xF0000000L) != 0)
            hash ^= (x >> 24);
        hash &= ~x;
    }
    return hash;
}

static dduint32
_hashfunc_BKDR(const char * dat, size_t size){
     dduint32 hash = 0;  dduint32 seed = 131; // 31 131 1313 13131 131313 etc..
    for(dduint32 i = 0; i < size; i++)
        hash = (hash * seed) + dat[i];
    return hash;
}

static dduint32
_hashfunc_SDBM(const char * dat, size_t size){
     dduint32 hash = 0;
    for(size_t i = 0; i < size; i++)
        hash = dat[i] + (hash << 6) + (hash << 16) - hash;
    return hash;
}

static dduint32
_hashfunc_DJB(const char * dat, size_t size){
     dduint32 hash = 5381;
    for(size_t i = 0; i < size; i++)
        hash = ((hash << 5) + hash) + dat[i];
    return hash;
}

static dduint32
_hashfunc_DEK(const char * dat, size_t size){
     dduint32 hash = (dduint32)size;
    for(size_t i = 0; i < size; i++)
        hash = ((hash << 5) ^ (hash >> 27)) ^ dat[i];
    return hash;
}

static ddcl_MapKeyHashFn g_hash_ways[] = {
    _hashfunc_AP,       // 0
    _hashfunc_RS,       // 1
    _hashfunc_JS,       // 2
    _hashfunc_PJW,      // 3
    _hashfunc_ELF,      // 4
    _hashfunc_BKDR,     // 5
    _hashfunc_SDBM,     // 6
    _hashfunc_DJB,      // 7
    _hashfunc_DEK,      // 8
};

static int
_default_cmp_fn(const void * k1, size_t sz1, const void * k2, size_t sz2){
    if(k1 == k2){ return 1; }
    if(sz1 != sz2){ return 0; }
    return strncmp(k1, k2, sz1) == 0;
}

DDCLAPI dduint32
ddcl_hash(const char * k, size_t sz, int type){
    return g_hash_ways[type](k, sz);
}

DDCLAPI dduint32
ddcl_map_hash(const char * k, size_t sz){
    return g_hash_ways[DDHASH_DEK](k, sz);
}


typedef struct tag_Node{
    const char * k;
    size_t ksz;
    const void * v;
    dduint32 hash;
    int next;
}Node;

struct tag_ddcl_Map{
    Node * slot;
    size_t slot_cap;
    int free_node;
    size_t count;
    size_t iter;
    ddcl_MapKeyCmpFn cmp_fn;
    ddcl_MapKeyHashFn hash_fn;
};

static int
find_free_slot (ddcl_Map * map){
    while(map->free_node > 0){
        map->free_node--;
        if(!map->slot[map->free_node].k){
            return map->free_node;
        }
    }
    return -1;
}

#define main_slot(map, hash) (hash % map->slot_cap)
#define get_node(map, i) (&(map->slot[i]))

static inline void
reset_free_node (ddcl_Map * map){
    while(map->free_node > 0){
        map->free_node --;
        if(!get_node(map, map->free_node)->k){
            break;
        }
    }
}

static Node *
new_node (ddcl_Map * map, dduint32 hash){
    int pos = main_slot(map, hash);
    Node * n = get_node(map, pos);
    if(n->k){
        pos  = find_free_slot(map);
        if(pos == -1){ return NULL; }
        while(n->next >= 0){
            n = get_node(map, n->next);
        }
        n->next = pos;
        n = get_node(map, pos);
    }
    if(pos == (map->free_node - 1)){
        reset_free_node(map);
    }
    return n;
}


static void
repos_node (ddcl_Map * map, Node * n){
    Node * rn = new_node(map, n->hash);
    *rn = *n;
    rn->next = -1;
}

static void
resize_slot (ddcl_Map * map, size_t cap){
    if(map->slot_cap == 0 || map->slot_cap == cap){
        return;
    }
    if(cap == 0){
        ddcl_free(map->slot);
        map->slot_cap = 0;
        return;
    }
    size_t old_cap = map->slot_cap;

    Node * old_slot = map->slot;
    map->slot = ddcl_malloc(sizeof(Node) * cap);
    memset(map->slot, 0, sizeof(Node) * cap);
    map->slot_cap = cap;
    map->free_node = cap;

    Node * n;
    for(int i = 0; i < old_cap; i ++){
        n = &(old_slot[i]);
        if(n->k){ repos_node(map, n); }
    }
    ddcl_free(old_slot);
}

static size_t
optimize_cap (size_t cap){
    for(int i = 1; ; i ++){
        if((1 << i) >= cap){
            return 1 << i;
        }
    }
    return 0;
}

DDCLAPI ddcl_Map *
ddcl_new_map(size_t cap){
    ddcl_Map * map = ddcl_malloc(sizeof(ddcl_Map));
    memset(map, 0, sizeof(ddcl_Map));
    cap = optimize_cap(cap);
    map->slot = ddcl_malloc(sizeof(Node) * cap);
    memset(map->slot, 0, sizeof(Node) * cap);
    map->slot_cap = cap;
    map->free_node = cap;
    map->cmp_fn = _default_cmp_fn;
    map->hash_fn = ddcl_map_hash;
    return map;
}

DDCLAPI void
ddcl_free_map(ddcl_Map * map){
    if(map->slot_cap){
        for(int i = 0; i < map->slot_cap; i ++){
            Node * n = &(map->slot[i]);
            if(n->k){
                ddcl_free((void *)n->k);
            }
        }
        ddcl_free(map->slot);
    }
    ddcl_free(map);
}

DDCLAPI void
ddcl_expand_map(ddcl_Map * map, size_t cap){
    cap += map->count;
    if(cap <= map->slot_cap){ return; }
    resize_slot(map, optimize_cap(cap));
}

DDCLAPI void
ddcl_put_map (ddcl_Map * map,
        const void * k, size_t ksz, const void * v){
    dduint32 hash = map->hash_fn((const char *)k, ksz);
    Node * n = get_node(map, main_slot(map, hash));
    while (n && n->k) {
        if (n->hash == hash &&
            map->cmp_fn(n->k, n->ksz, k, ksz)) {
            break;
        }
        else {
            n = n->next >= 0 ? get_node(map, n->next) : NULL;
        }
    }
    if(n && n->k){ n->v = v; return; }
    n = new_node(map, hash);
    if(!n){
        resize_slot(map, map->slot_cap * 2);
        n = new_node(map, hash);
    }
    n->k = k;
    n->ksz = ksz;
    n->hash = hash;
    n->next = -1;
    n->v = v;
}

DDCLAPI int
ddcl_del_map (ddcl_Map * map, const void * k, size_t ksz){
    dduint32 hash = map->hash_fn((const char *)k, ksz);
    int pos = main_slot(map, hash);
    Node * main = get_node(map, pos);
    if (!main->k) { return 0; }
    Node * n = main;
    Node * pre = main;
    while(n){
        if(n->hash == hash && 
            map->cmp_fn(n->k, n->ksz, k, ksz)){
            break;
        }else{
            pos = n->next;
            n = n->next >= 0 ? get_node(map, n->next):NULL;
        }
    }
    if(!n){ return 0; }
    map->count --;
    if(n == main){
        n = n = n->next >= 0 ? get_node(map, n->next):NULL;
        if(n){
            *main = *n;
            n->k = NULL;
        }else{
            main->k = NULL;
        }
    }else{
       n->k = NULL;
       if (pre) { pre->next = n->next; }
       n->next = -1;
    }
    if (pos >= map->free_node) {
        map->free_node = pos + 1;
    }
    return 1;
}

DDCLAPI int
ddcl_get_map(ddcl_Map * map,
        const void * k, size_t ksz, const void ** v){
    dduint32 hash = map->hash_fn((const char*)k, ksz);
    Node * main = get_node(map, main_slot(map, hash));
    if (!main->k) { return 0; }
    Node * n = main;
    while(n){
        if(n->hash == hash && 
            map->cmp_fn(n->k, n->ksz, k, ksz)){
            break;
        }else{
            n = n->next >= 0 ? get_node(map, n->next):NULL;
        }
    }
    if(n){ *v = n->v; return 1; }
    else{ return 0; }
}

DDCLAPI size_t
ddcl_count_map (ddcl_Map * map){
    return map->count;
}

DDCLAPI void
ddcl_begin_map (ddcl_Map * map){
    map->iter = 0;
}

DDCLAPI int
ddcl_next_map (ddcl_Map * map,
    const void ** k, size_t * ksz, const void ** v){
    Node * n;
    for(;;){
        if(map->iter >= map->slot_cap){ return 0; }
        n = get_node(map, map->iter);
        map->iter ++;
        if(n->k){
            *k = n->k;
            *ksz = n->ksz;
            *v = n->v;
            return 1;
        }
    }
    return 0;
}
